select k th mimimum from array a[0..n-1]

Posted by davit-datuashvili on Stack Overflow See other posts from Stack Overflow or by davit-datuashvili
Published on 2010-06-05T10:28:50Z Indexed on 2010/06/05 10:32 UTC
Read the original article Hit count: 124

Filed under:

i have done folloing code from progrmming pearls here is code

import java.util.*;
public class select {
public static int select1(int x[],int l,int u,int k){
    //pre l<=k<=u
    //post x[l..k-1]<=x[k]<=x[k+1..u]
    Random r=new Random();
   int  t=r.nextInt(u-1-l)+l;
     if (l>=u) return -1 ;
    swap(l,t);
    int s=x[l];
    int i=l;
     int j=u+1;
       while (true){
         do
         {
              i++;
         }while (i<=u && x[i]<t);
         do
         {
              j--;
         }while (x[j]>t);
          if (i>j)  break;
           int temp=x[i]; x[i]=x[j];x[j]=t;
            swap(l,j);

             if (j<k){
               return   select1(x,j+1,u,k);

         }
       }
            return    select1(x,l,j-1,k);
           }

    public static void main(String[] args) {
        int x[]=new int[]{4,7,9,3,2,12,13,10,20};
                  select1(x,0,x.length-1,5);

    }



    public static void swap(int i,int j){
        int c=i;
        i=j;
        j=c;



    }
}

but here is mistake

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
        at select.select1(select.java:21)
        at select.main(select.java:36)
Java Result: 1

please help

© Stack Overflow or respective owner

Related posts about algorithm